package com.lw.leetcode.tree.a;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 257. 二叉树的所有路径
 *
 * @Author liw
 * @Date 2021/4/16 15:28
 * @Version 1.0
 */
public class BinaryTreePaths {
    public static void main(String[] args) {

        TreeNode a = new TreeNode(21);
        TreeNode b = new TreeNode(32);
        TreeNode c = new TreeNode(43);
        TreeNode d = new TreeNode(654);
        TreeNode e = new TreeNode(75);
        TreeNode f = new TreeNode(86);
        a.left = b;
        a.right = c;
        b.right = d;
        b.left = f;
        c.left = e;

        List<String> strings = new BinaryTreePaths().binaryTreePaths(a);
        strings.forEach(System.out::println);

    }

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        StringBuilder sb = new StringBuilder();
        find(root, list, sb, 0);
        return list;
    }

    // 调整
    private static void find(TreeNode root, List<String> list, StringBuilder sb, int n) {
        String value = "->" + root.val;
        int length = value.length();
        sb.append(value);
        if (root.left == null && root.right == null) {
            list.add(sb.substring(2));
            sb.delete(n, sb.length());
            return;
        }
        if (root.left != null) {
            find(root.left, list, sb, n + length);
        }
        if (root.right != null) {
            find(root.right, list, sb, n + length);
        }
        sb.delete(n, sb.length());
    }

}
